46. Permutations
Medium

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

 

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

 

Constraints:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All the integers of nums are unique.
Accepted
837.8K
Submissions
1.2M
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 3.77 (91 votes)

Premium

Solution


Approach 1: Backtracking

Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, i.e. backtracks and then try again.

Here is a backtrack function which takes the index of the first integer to consider as an argument backtrack(first).

  • If the first integer to consider has index n that means that the current permutation is done.
  • Iterate over the integers from index first to index n - 1.
    • Place i-th integer first in the permutation, i.e. swap(nums[first], nums[i]).
    • Proceed to create all permutations which starts from i-th integer : backtrack(first + 1).
    • Now backtrack, i.e. swap(nums[first], nums[i]) back.
Current
1 / 14

Complexity Analysis

  • Time complexity : O(k=1NP(N,k))\mathcal{O}(\sum_{k = 1}^{N}{P(N, k)}) where P(N,k)=N!(Nk)!=N(N1)...(Nk+1)P(N, k) = \frac{N!}{(N - k)!} = N (N - 1) ... (N - k + 1) is so-called k-permutations_of_n, or partial permutation.

Here first+1=kfirst + 1 = k for the expression simplicity. The formula is easy to understand : for each kk (each firstfirst) one performs N(N1)...(Nk+1)N(N - 1) ... (N - k + 1) operations, and kk is going through the range of values from 11 to NN (and firstfirst from 00 to N1N - 1).

Let's do a rough estimation of the result : N!k=1NN!(Nk)!=k=1NP(N,k)N×N!N! \le \sum_{k = 1}^{N}{\frac{N!}{(N - k)!}} = \sum_{k = 1}^{N}{P(N, k)} \le N \times N!, i.e. the algorithm performs better than O(N×N!)\mathcal{O}(N \times N!) and a bit slower than O(N!)\mathcal{O}(N!).

  • Space complexity : O(N!)\mathcal{O}(N!) since one has to keep N! solutions.

Report Article Issue

Comments: 69
beginner_7's avatar
Read More

Thank you for the animation! Makes everything clear!
image

103
Show 2 replies
Reply
Share
Report
qqwei's avatar
Read More

For the complexity, I think you can explain in this way: in the first level of the tree, you have N options and for each of the option, you have N-1 option, and for each of these N-1 options, you have another N-2 options, so putting them together you would end up N*(N-1)*(N-2).... = N!

80
Show 3 replies
Reply
Share
Report
s961206's avatar
Read More

I think the time complexity is O(n x n!) instead of O(n!), since you will have n! permutation. And, for each permutation, you run exact n recursive call to reach it. So it should be n x n! ?

129
Show 21 replies
Reply
Share
Report
junhaowanggg's avatar
Read More

First, I think the time complexity should be N x N!.

Initially we have N choices, and in each choice we have (N - 1) choices, and so on. Notice that at the end when adding the list to the result list, it takes O(N).

Second, the space complexity should also be N x N! since we have N! solutions and each of them requires N space to store elements.

70
Show 3 replies
Reply
Share
Report
calvinchankf's avatar
Read More

honestly, i dont really know how to analyze the time complexity of this approach. I understand the nPk part, but how can to come up with the summation and how can i present it to the interviewer?

27
Show 2 replies
Reply
Share
Report
alphaorc's avatar
Read More

For those interested, this is called Heap's Algorithm.

55
Show 1 reply
Reply
Share
Report
douer233's avatar
Read More

Anyone can explain why the there should be output.append(nums[:]) but not nums?

13
Show 3 replies
Reply
Share
Report
bobxu1128's avatar
Read More

why we need the second swap?

18
Show 5 replies
Reply
Share
Report
harsh161's avatar
Read More

Hello,
Can anyone explain why space complexity is O(N!) (factorial here) ? Shouldn't it be O(N) only (the depth of recursive tree) for Java program at least ?

My thinking here: At every index i, we go down the depth level from (i+1) to N and recurse back, pop off stack and go down path (i+2) to N and recurse back and so on.. Based on diagram also, we go at most N levels down and recurse back before going to another path. So I was thinking we will have a balanced tree kind of situation here. Please correct me if I'm wrong.

Secondly, when we reach last level shouldn't we consider time complexity of creating a new ArrayList of N numbers to be added to result ?

11
Show 6 replies
Reply
Share
Report
junpitt's avatar
Read More

For the space complexities, I think you're mixing two different types of space complexities. One is the additional memory it uses to solve a problem. For this question, since the nature of the problem is a DFS, so that space complexity is O(N).

For your analysis of O(N!), it is the actual space complexity for the solution itself....

5
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/08/2021 20:12Accepted8 ms8.3 MBcpp
04/28/2021 09:08Accepted4 ms8.2 MBcpp
08/21/2020 09:18Accepted4 ms8.5 MBcpp
05/06/2020 09:48Accepted24 ms14 MBpython3
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium